def linear_search(arr, target):
    """
    线性查找算法
    :param arr: 待查找的列表
    :param target: 要查找的目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 示例使用
data = [4, 2, 7, 1, 9, 5, 3]
target_value = 7

result = linear_search(data, target_value)
print(f"元素 {target_value} 的索引是: {result}" if result != -1 else "元素未找到")


def binary_search(arr, target):
    """
    二分查找算法
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


# 示例使用
sorted_data = sorted([4, 2, 7, 1, 9, 5, 3])  # 二分查找需要有序列表
target_value = 5

result = binary_search(sorted_data, target_value)
print(f"元素 {target_value} 的索引是: {result}" if result != -1 else "元素未找到")


def binary_search_recursive(arr, target, left, right):
    """
    递归实现的二分查找
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :param left: 当前搜索区间的左边界
    :param right: 当前搜索区间的右边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


# 示例使用
sorted_data = sorted([4, 2, 7, 1, 9, 5, 3])
target_value = 3

result = binary_search_recursive(sorted_data, target_value, 0, len(sorted_data) - 1)
print(f"元素 {target_value} 的索引是: {result}" if result != -1 else "元素未找到")









import time

# 创建一个大型有序列表
large_data = list(range(1, 10000001))  # 1到10,000,000

# 测试线性查找
target = 9999999
start_time = time.time()
result = linear_search(large_data, target)
end_time = time.time()
print(f"线性查找耗时: {end_time - start_time:.6f}秒")

# 测试二分查找
start_time = time.time()
result = binary_search(large_data, target)
end_time = time.time()
print(f"二分查找耗时: {end_time - start_time:.6f}秒")


def binary_search_iterative(arr, target):
    """
    迭代实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # 计算中间索引
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # 目标在右半区
        else:
            right = mid - 1  # 目标在左半区
    return -1  # 未找到


def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的右边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1  # 基线条件：未找到

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的右边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1  # 基线条件：未找到

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的右边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1  # 基线条件：未找到

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


import time
import random


def compare_search_performance(list_size, target_position='middle'):
    """
    比较两种查找算法的性能
    :param list_size: 列表大小
    :param target_position: 目标位置 ('first', 'middle', 'last', 'random', 'nonexistent')
    """
    # 创建有序测试数据
    test_data = sorted([random.randint(0, 10000000) for _ in range(list_size)])

    # 根据参数设置目标值
    if target_position == 'first':
        target = test_data[0]
    elif target_position == 'middle':
        target = test_data[len(test_data) // 2]
    elif target_position == 'last':
        target = test_data[-1]
    elif target_position == 'random':
        target = random.choice(test_data)
    else:  # nonexistent
        target = -1  # 确保不存在于列表中

    print(f"\n测试列表大小: {list_size:,} 元素")
    print(f"目标位置: {target_position}")

    # 测试线性查找
    start = time.perf_counter()
    result = linear_search(test_data, target)
    linear_time = time.perf_counter() - start
    print(f"线性查找: 结果={result}, 耗时={linear_time:.6f}秒")

    # 测试迭代二分查找
    start = time.perf_counter()
    result = binary_search_iterative(test_data, target)
    binary_iter_time = time.perf_counter() - start
    print(f"迭代二分查找: 结果={result}, 耗时={binary_iter_time:.6f}秒")

    # 测试递归二分查找
    start = time.perf_counter()
    result = binary_search_recursive(test_data, target)
    binary_rec_time = time.perf_counter() - start
    print(f"递归二分查找: 结果={result}, 耗时={binary_rec_time:.6f}秒")

    # 计算速度比
    if linear_time > 0 and binary_iter_time > 0:
        ratio = linear_time / binary_iter_time
        print(f"迭代二分查找比线性查找快 {ratio:.1f} 倍")






# 小规模测试 (1万元素)
compare_search_performance(10_000, 'middle')

# 中等规模测试 (10万元素)
compare_search_performance(100_000, 'last')

# 大规模测试 (100万元素)
compare_search_performance(1_000_000, 'random')

# 超大规模测试 (1000万元素)
compare_search_performance(10_000_000, 'first')

# 测试不存在的元素
compare_search_performance(1_000_000, 'nonexistent')





